﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Ndo.Maths.MOP
{
    /// <summary>
    /// Strenghth Pareto Evolutionary Algothm 
    /// </summary>
    /// <typeparam name="Individual"></typeparam>
    /// <typeparam name="Vector"></typeparam>
    public class SPEA2<Individual, Vector> : MOEA<Individual, Vector>
        where Individual : XY<Vector, Vector>, new()
        where Vector : class, IList<double>, ICloneable
    {
        public SPEA2()
        {
            //cache = new DominationCacheWithRelations(base.Domination);
            Selection = StrengthSelection;
            Evaluation = new KthNeighborCrowdingEvaluation<Vector>(Measure.EuclideanDistance);
            PopulationChanged += PC;
        }
        private int elitistScale = -1;
        public int ElitistScale { get { return elitistScale < 0 ? this.ScaleLimit / 2 : elitistScale; } set { elitistScale = value; } }

        //protected DominationCacheWithRelations cache;
        //public override DominationTypes Domination(Vector a, Vector b)
        //{
        //    return cache.Domination(a, b);
        //}
        private void PC(EA<Individual, Vector, Vector> ea)
        {
            int[] ranks = GetRanks(new List<Individual>(Population));
            int count = 0;
            List<double> list = new List<double>();
            foreach (int i in ranks)
            {
                if (i == 0)
                    count++;
                list.Add(i);
            }
            ST st = new ST();
            st.Add(list);
            Console.WriteLine("GN[{0}] ---> domination count: {1}; S: {2}({3}); NondominatedSet proportion: {4}", GenerationNumber, GetDominatingCount(), st.Mean, st.Deviation, (double)count / (double)Population.Count);
        }

        public int[] GetRanks(IList<Individual> inds)
        {
            int n = inds.Count;
            //foreach (Individual ind1 in inds)
            //{
            //    if(cache.GetRelation(ind1.Y) == null)
            //        foreach (Individual ind2 in inds)
            //        {
            //            cache.Domination(ind1.Y, ind2.Y);
            //        }
            //}
            //int[] R = new int[n];
            //for(int i=0; i<n; i++)
            //{
            //    ICollection<Vector>[] r = cache.GetRelation(inds[i].Y);
            //    if(r != null && r[0] !=null)
            //    {
            //        foreach (Vector vector in r[0])
            //        {
            //            ICollection<Vector>[] r2 = cache.GetRelation(vector);
            //            if (r2 != null && r2[2] != null)
            //                R[i] += r2[2].Count;
            //        }
            //    }
            //}
            int[] S = new int[n], R = new int[n];
            bool[,] bs = new bool[n,n];
            for(int i=0; i<n; i++)
            {
                Vector v1 = inds[i].Y;
                for(int j=0; j<n; j++)
                {
                    if (bs[i, j] = Domination(v1, inds[j].Y) == DominationTypes.Dominate)
                        S[i]++;
                }
            }
            for(int i=0; i<n; i++)
            {
                for(int j=0; j<n; j++)
                {
                    if (bs[j, i])
                        R[i] += S[j];
                }
            }
            return R;
        }

        public IList<Individual> StrengthSelection(IList<Individual> inds, int limit)
        {
            if (limit == 0)
                return new Individual[0];
            int n = inds.Count;
            if (limit >= n)
                return new List<Individual>(inds);
            int[] ranks = GetRanks(inds);
            Individual[] list = new Individual[n];
            inds.CopyTo(list,0);
            Array.Sort(ranks, list);
            int pareto = 0, paretolimit = ElitistScale, i=0;
            while (pareto < n && ranks[pareto] == 0) pareto++;
            Stack<Individual> ret = new Stack<Individual>();
            if (pareto > paretolimit)
            {
                Vector[] ps = new Vector[pareto];//, ev = new Vector[n - pareto];
                Dictionary<Vector, Individual> dict = new Dictionary<Vector, Individual>(new RefEqualityComparer());
                for (i = 0; i < pareto; i++)
                    dict[ps[i] = list[i].Y] = list[i];
                foreach (Vector vector in Evaluation.Prune(ps, paretolimit))
                {
                    ret.Push(dict[vector]);
                };
                i = paretolimit;
            }
            while (ret.Count < limit)
            {
                ret.Push(list[i++]);
            }
            --i;
            if (ranks[i] == ranks[i + 1])
            {
                int r = ranks[i], len = i + 2;
                while (len<n && ranks[len] == r)
                    len++;
                while (--i>=0 && ranks[i] == r)
                    ret.Pop();
                r = len;
                len = len - i - 1;
                Vector[] ps = new Vector[len], ev = new Vector[n-len];
                Dictionary<Vector, Individual> dict = new Dictionary<Vector, Individual>(new RefEqualityComparer());
                for (int i0 = 0, i1 = 0, i2 = 0; i0 < n; i0++)
                {
                    if (i0 > i && i0 < r)
                        ps[i1++] = list[i0].Y;
                    else
                        ev[i2++] = list[i0].Y;
                    dict[list[i0].Y] = list[i0];
                }
                foreach (Vector vector in Evaluation.Prune(ps, limit - ret.Count, ev))
                {
                    ret.Push(dict[vector]);
                }
            }
            //clear unuseful cache
            //Dictionary<Individual, object> map = new Dictionary<Individual, object>();
            //foreach (Individual ind in ret)
            //{
            //    map[ind] = null;
            //}
            //foreach (Individual ind in inds)
            //{
            //    if(!map.ContainsKey(ind))
            //        cache.Remove(ind.X);
            //}
            return ret.ToArray();
        }
    }
}
